package com.vint.leetcode;

import com.vint.common.ListNode;
import com.vint.common.TreeNode;

import java.util.List;

/*
 * 1. done
 * 2. easy
 */
public class Leetcode109 {
	public TreeNode sortedListToBST(ListNode head) {
		if(head==null)return null;
		if(head.next==null)return new TreeNode(head.val);
		ListNode mid = getMid(head);
		TreeNode root = new TreeNode(mid.val);
		ListNode afte = mid.next;
		mid.next = null;
		root.right= sortedListToBST(afte);
		root.left = sortedListToBST(head);
		return root;
	}
	public ListNode getMid(ListNode root){
		if(root==null || root.next ==null) return root;
		ListNode mid = root;
		ListNode pre = root.next;
		while(pre!=null&&pre.next!=null){
			mid = mid.next;
			pre = pre.next.next;
		}
		return mid;
	}
}
